Triangulating random and scattered two-dimensional points on a plane has been the subject of significant research in the past few decades. Triangulating techniques can be used for digital terrain modeling, as well as for mathematical calculations such as fluid flow and heat transfer, and data visualization and rendering. The origins of triangulating data points go back to Voronoi and to Delaunay, and a number of textbooks and papers have extensively covered their properties and algorithms for their constructions. See, for example, M. Shamos, Computational geometry, PhD Thesis, Yale University, New Haven, Conn., 1977; F. Preparata and M. Shamos, Computational Geometry--An Introduction, Springer-Verlag, New York, N.Y., 1985; H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, New York, N.Y., 1987; D. Rhynsburger, Analytic delineation of Theissen polygons, Geographical Analysis, Vol. 5, No. 2, 1973, pp 133-144; and P. J. Green and R. Sibson, Computing Dirichlet tessellations in the plane, The Computer Journal, Vol 21, No. 2, 1978, pp 168-173.
Most of these papers and books deal with theoretical aspects of the algorithms and give upper bounds on their complexity. Using the widely accepted divide-and-conquer method, one can triangulate a set of points in .theta.(n logn) time. Recent research in computational geometry has gone into decreasing this bound further down in the hope that practical implementation will provide faster execution time.